import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        System.out.println(solution.generateParenthesis(1));
    }
}

//官方题解方法三
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        return generate(n);
    }

    List[] cache = new List[9];

    List<String> generate(int n) {
        if(cache[n] != null){
            return cache[n];
        }
        if(n == 0){
            cache[n] = new ArrayList<>();
            cache[n].add("");
            return cache[n];
        }

        List<String> ans = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(String left: generate(i)){
                for(String right: generate(n - i - 1)){
                    ans.add('(' + left + ')' + right);
                }
            }
        }
        cache[n] = ans;
        return ans;
    }
}

//官方题解方法二
class Solution1 {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        generate(n, stringBuilder, 0, 0, ans);
        return ans;
    }

    void generate(int n, StringBuilder cur, int left, int right, List<String> ans){
        if(cur.length() == 2 * n){
            ans.add(cur.toString());
        }

        if(left < n){
            cur.append('(');
            generate(n, cur, left + 1, right, ans);
            cur.deleteCharAt(cur.length() - 1);
        }
        if(right < left){
            cur.append(')');
            generate(n, cur, left, right + 1, ans);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}